#include <bits/stdc++.h>

using namespace std;

/**
每次洗牌：
1. 偶数位提前
2. 取前k个
 */

class Solution {
public:
    vector<int> mp;
    vector<int> next;
    /*洗牌一次*/
    void Disruption(int s){
        //把偶数位放到奇数位之前
        queue<int> q;
        int num=0,pre=s;
        for(int i=next[s];i!=-1;i=next[i]){
            num++;
            if(num%2==0){
                q.push(i);
                next[pre]=next[i];
            }
            pre=i;
        }
        int x=next[s],cur=s;
        while(!q.empty()){
            next[cur]=q.front();
            q.pop();
            cur=next[cur];
        }
        next[cur]=x;

        // for(int i=next[s];i!=-1;i=next[i]){
        //     cout << mp[i] << " ";
        // }  cout <<endl;

        
    }

    bool isMagic(vector<int>& target) {
        int len=target.size();
        mp=vector<int>(len+1,0);
        next=vector<int>(len+1,0);
        for(int i=0;i<=len;i++){
            mp[i]=i;
            next[i]=i+1;
        }
        next[len]=-1;
        Disruption(0);
        int k=0,pre=0;
        for (int i = next[0]; i !=-1 && mp[i]==target[k] ; i=next[i])
        {
            k++;
            pre=i;
        }
        if(0==k){
            return false;
        }
        int cur=k; 
            // for(int i=next[0]; i!=-1;i=next[i]){
            //     cout << mp[i] << " ";
            // }cout <<endl;
            // cout << k <<endl;
        //cur标记当前遍历长度
        //pre 代表当前指针位置
        //k为打乱的长度
        while(cur<=len ){
            Disruption(pre);

            // for(int i=next[0]; i!=-1;i=next[i]){
            //     cout << mp[i] << " ";
            // }cout <<endl;

            int k1=0;
           
            for(int i=next[pre];i!=-1 && mp[i]==target[cur+k1]&& k1<k;i=next[i]){
                // cout<< mp[i] << " " << target[cur+k1] << endl;
                k1++;
                pre=i;
            }
            cur+=k1;
            if(k1!=k && cur<len){
                return false;
            }else if(cur==len){
                break;
            }
        }
        return true;
    }
};

int main(){
    freopen("out.txt","w",stdout);
    Solution s;
    //  vector<int> v={2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,35,41,33,39,37,47,43,45};
    vector<int> v={1,2,3,4,5};
   cout <<  (s.isMagic(v)?"true":"false") << endl;;



    return 0;
}